package com.datastructure.test.reversekgrouplistnode;

import java.util.ArrayList;

public class ReverseKGroupListNode {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next=new ListNode(2);
        listNode.next.next=new ListNode(3);
        listNode.next.next.next=new ListNode(4);
        listNode.next.next.next.next=new ListNode(5);
        ReverseKGroupListNode reverseKGroupListNode = new ReverseKGroupListNode();
        ListNode listNode1 = reverseKGroupListNode.reverseKGroup(listNode, 3);
        System.out.println(listNode1);
    }

    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if(k==1){
            return head;
        }
        int nodeLength = getListNodeLength(head);
        if(nodeLength<k){
            return head;
        }
        if(nodeLength==k){
            return reverseListNode(head)[0];
        }
        int time = nodeLength/k;
        ArrayList<ListNode[]> data = new ArrayList<>();
        ListNode nextListNode=head;
        ListNode lastListNode;
        ListNode cur;
        for (int i = 0; i < time; i++) {
            lastListNode=nextListNode;
            cur=lastListNode;
            int K = k;
            while (K>1){
                K--;
                cur=cur.next;
            }
            nextListNode=cur.next;
            cur.next=null;
            data.add(reverseListNode(lastListNode));
        }
        data.get(data.size()-1)[1].next=nextListNode;
        for (int i = 0; i < data.size()-1; i++) {
            data.get(i)[1].next=data.get(i+1)[0];
        }
        return data.get(0)[0];
    }

    public int getListNodeLength(ListNode head){
        int sum = 0;
        while (head!=null){
            sum++;
            head=head.next;
        }
        return sum;
    }

    public ListNode[] reverseListNode(ListNode head){
        ListNode[] data = new ListNode[2];
        ListNode res = null;
        ListNode cur = head;
        boolean flag=true;
        while (cur!=null){
            ListNode temp = cur.next;
            if(flag){
                data[1]=cur;
                flag=false;
            }
            cur.next=res;
            res=cur;
            cur=temp;
        }
        data[0]=res;
        return data;
    }
}

class ListNode {
   int val;
   ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}
